שני סבבי ראיונות שני ראיונות בכל אחד ראיונות טכנים
שאלות מתוך הראיון
נתון מערך של זוגות ומספר אחד בלי זוג. איך תמצא את המספר הנל?
תשובות
הוסף תשובה
|
לצפיה בתשובות
מאי 2019
פתרון ראשון: מעבר לינארי על איברי המערך וXOR ביניהם, האיבר היחיד שהביטים שלא לא יתבטלו עם בן הזוג שלו הוא האיבר הבודד, ולכן בתום הפעולה נישאר עם האיבר הבודד.
פתרון שני: במערך לכל איבר יש בן זוג למעט איבר אחד בלבד -> מכאן שמספר איברי המערך אי-זוגי בהכרח.
לכן ניתן לעשות PIVOT סביב החציון ולבחור בחצי בגודל האי-זוגי ולהמשיך ברקרוסיה עד שנישאר עם מערך בגודל 2 ומערך בגודל 1, האיבר הבודד הוא האיבר שאין לו בן זוג. סיבוכיות הזמן במקרה הזה תיהיה גם כן לינארית בכלל הקפיצות האקספוננציאליות. אך בגלל הקבוע הגדול הפתרון הראשון עדיף.
ראיון לתפקיד 
